package com.example.zzy.zzytest.algo.sort.n2sort;

import static com.example.zzy.zzytest.test.LeeTest.exch;

/**
 * 插入排序，分左侧有序和右侧无序，每次从无序取第一个往有序部分合适的位置插入
 * 对几乎已经排好序的效率高
 * 但一般来说低效，因为每次只能移动一位
 */
public class InsertSort {
    public static void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {

            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
                exch(arr, j - 1, j);
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3, 1, 5, 0, 6, 2};
        sort(nums);

//        3,1,5,0,6,2
//        1,3,5,0,6,2
//        0,1,3,5,6,2
    }
}
